1. Field of the Invention
The present invention relates to an apparatus and method for multidimensional memory resource management and allocation. More particularly, the present invention relates to an apparatus and method for memory resource management and allocation of multidimensional memory spaces in an efficient manner that does not exceed overlap constraints for the multidimensional memory spaces.
2. Description of the Related Art
Computing devices and electronic devices having computing capabilities, such as Personal Computers (PCs), laptops, mobile terminals, portable electronic devices, electronic books, personal media players, smart appliances, and a wide variety of other devices having computing capabilities have become ubiquitous. Additionally, consumer demand for increasing computing and/or processing capabilities of such devices has rapidly increased as communication networks and bandwidth have increased and as portability and capabilities of the computing and electronic devices have increased. Accordingly, there is a need for increased performance for memory and more efficient management of memory resources, included in the computing and electronic devices.
Managing allocated and/or unallocated blocks of a 1-Dimensional (1D) memory resource according to the related art may be a relatively simple task because both the 1D memory resource and the allocated and/or unallocated blocks are organized in a linear manner. Thus, a 1D memory manager may efficiently find available memory resources for a memory request of an arbitrary size because the 1D memory manager starts allocation with the entirety of the 1D memory resource being available, and sequentially breaks up no more than one block of unallocated blocks for each allocation request. Thus, in the case of the 1D memory resource, for each allocation, only a trivial amount of work may be needed in order to maintain a list of unallocated resources in a quasi and/or fully sorted order, thus allowing for any subsequent search for available memory resources of an appropriate size to be done quickly.
Because the allocated and/or unallocated blocks of the 1D memory resource are disposed in a linear manner in which the 1D memory resource is also organized, then in a case where block edges touch or overlap, a resulting high-level map of allocated and/or unallocated blocks is in a form of lines, or in other words, is linear. However, such linear features are unique to 1D resources, and thus, allocation schemes and memory managers for 1D memory resources may be inadequate for efficient allocation of memory resources in a multidimensional memory resource. Additionally, the allocation schemes and memory managers for 1D memory resources may be especially inadequate in a 2 Dimensional (2D) system, such as a graphics display, which are physically manipulated in a 1D memory resource.
For example, in a case where pixels of a 2D canvas for a graphics display are organized linearly in a 1D memory resource, the neighboring pixels in a same row are sequentially located in the 1D memory resource, but neighboring pixels located in different, but adjacent, rows may be completely disconnected in a linear structure of the 1D memory resource. Thus, in such a case, if an allocation of a block having an arbitrary 2D shape, even a simple shape such as a rectangle, is requested, the 1D memory manager, and/or the 1D memory allocation scheme, may fail to efficiently locate unallocated blocks.
FIGS. 1A and 1B illustrate a 2D canvas of pixels allocated according to a 1D memory allocation scheme according to the related art.
Referring to FIGS. 1A and 1B, the 2D canvas 101 of a memory resource may have a height of 12 pixels and a width of 12 pixels, and has a first block 102 and a second block 103 of allocated pixels such that a total of 13 pixels are allocated. In the 2D canvas 101, when an allocation of a block of 5×5 pixels is requested, a 1D memory allocator may not find an appropriately sized unallocated block, from among the unallocated blocks 104 to 108 shown in FIG. 1B, in order to support the requested allocation of the block of 5×5 pixels. That is, because of the first block 102 and the second block 103, being disposed in the manner shown in FIG. 1A, the 1D memory allocator may only accommodate the request for the block of 5×5 pixels by allocating portions of at least three of the unallocated blocks 104 to 108 shown in FIG. 1B.
In order to address the above noted problems illustrated in FIGS. 1A and 1B, and in order to address needs of multidimensional memory resources, such as those used in display devices, that are linearly organized, multidimensional resource managers and/or allocators are needed in order to efficiently allocate resources for arbitrary shapes. An example of such resource allocation for arbitrary shapes, according to the related art, is a Wordle word clouding method, which allows for placement of words in a 2D word cloud according to a non-deterministic time algorithm.
The Wordle word clouding method may allow for no overlap of any characters of the pace words and dense nesting of characters when adding a new word by placing the new word at a random location in the word cloud and then repeatedly moving the new word outwardly along a spiral path until the new word, as displayed by pixels, does not collide with pixels used to display any existing words. While the Wordle word clouding method works well for word clouds of less than 100 words, the method may become very inefficient for word clouds having large numbers of words, such as 500 words, because the Wordle word clouding method has a non-deterministic allocation time. Although the Wordle word clouding method uses a random time for placement of a word, by moving the new word outwardly along a spiral path the Wordle word clouding method may prevent analyzing of duplicate positions. Accordingly, the Wordle word clouding method does not provide a deterministic time for allocation.
Accordingly, there is a need for a multidimensional resource manager and/or allocator that may efficiently allocate memory resources for requests of arbitrarily shaped blocks.